# 剑指Offer题解 - Day52

# 剑指 Offer 66. 构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

示例:

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

1
2

提示：

所有元素乘积之和不会溢出 32 位整数
a.length <= 100000

思路：

首先考虑暴力法求解。题目没有限制使用乘法，因此可以分别进行相乘获取结果数组。

# 暴力法

不难写出如下代码：

/**
 * @param {number[]} a
 * @return {number[]}
 */
var constructArr = function(a) {
    let res = [];
    for (let i = 0; i < a.length; i++) {
        let temp = 1;
        let j = 0;
        while(j < a.length) {
            if (j !== i) temp *= a[j];
            j++;
        }
        res.push(temp);
    }
    return res;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度 O(n^2)。
空间复杂度 O(n)。

分析：

暴力法需要双层遍历，效率太低，而且无法通过提交。因此本方法不推荐使用，了解即可。

那如何才不需要双层遍历，同时不使用除法进行题解呢？双层遍历的效率低是因为没有合理利用重复相乘所得到的结果。

假设结果数组是每个元素相乘，然后当前元素置为 1 ，那么就可以组成一个如下的列表：

// 假设数组为[1,2,3,4,5]

1 2 3 4 5
1 1 3 4 5
1 2 1 4 5
1 2 3 1 5
1 2 3 4 1

1
2
3
4
5
6
7

分别迭代计算 下三角 和 上三角 两部分的乘积，就可以得出最终结果。

# 前缀和

/**
 * @param {number[]} a
 * @return {number[]}
 */
var constructArr = function(a) {
    let length = a.length; // 缓存数组的长度
    if (!length) return []; // 如果数组为空，则直接返回空数组
    let b = Array.from({ length }); // 初始化指定长度的数组
    b[0] = 1;
    let temp = 1;
    for (let i = 1; i < length; i++) { // 计算下三角
        b[i] = b[i - 1] * a[i - 1];
    }
    for (let i = length - 2; i >= 0; i--) { // 计算上三角
        temp *= a[i + 1];
        b[i] *= temp;
    }
    return b;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度 O(n)。
空间复杂度 O(1)。

分析：

该方法的难点在于如何计算下三角和上三角。同时避免计算a[i] 。

首先来看下三角。初始化b[0] = 1 ，然后计算b[1]及以后的值。计算方式就是用b[i - 1] 来存储上一次循环的乘积。使用存储的乘积再乘以a[i - 1] ，再赋值给b[i] 本身。下三角循环完毕后，b数组里存储的就是下三角元素的乘积。

再来看上三角。因为我们要避开a[i] ，因此这里默认从倒数第二个元素开始循环。而且下三角已经将b元素的最后一项计算正确了。使用变量temp 来保存上三角的乘积。累计相乘后，每次循环的最后再将存储的乘积与b数组当前元素进行相乘，最后得到的值就是最终结果。

计算完毕后，返回数组b。

# 总结

本题考查数学中的前缀和。核心原理就是存储前面计算好的乘积结果，防止大量的重复计算。同时要注意两次循环的下标初始值和a数组的下标取值。

复杂度方面，遍历了两次数组a，因此时间复杂度是O(n) 。声明了常数级别的常量，b数组是返回值，因此不计算复杂度，所以空间复杂度是O(1) 。

剑指Offer题解 - Day51 剑指Offer题解 - Day53